#pragma once

namespace solution_092
{

struct ListNode
{
    int val;
    ListNode* next;
    ListNode() : val(0), next(nullptr) { }
    ListNode(int x) : val(x), next(nullptr) { }
    ListNode(int x, ListNode* next) : val(x), next(next) { }
};

class Solution
{
public:
    ListNode* reverseBetween(ListNode* head, int m, int n)
    {
        if (head == nullptr || head->next == nullptr || m == n)
            return head;

        ListNode root(0, head);
        auto before = &root;
        int i = 1;
        while (i < m) {
            before = before->next;
            ++i;
        }

        auto prev = before->next;
        auto node = prev->next;

        while (i < n) {
            auto next = node->next;
            node->next = prev;
            
            prev = node;
            node = next;
            ++i;
        }

        before->next->next = node;
        before->next = prev;
        return root.next;
    }
};

}  /* namespace solution_092 */
